package com.yitiao.data_algorithms.leetcode.editor.cn;

import com.yitiao.data_algorithms.leetcode.editor.cn.base.ListNode;
import com.yitiao.data_algorithms.leetcode.editor.cn.base.TreeNode;

class RotateList {
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     * public class ListNode {
     * int val;
     * ListNode next;
     * ListNode() {}
     * ListNode(int val) { this.val = val; }
     * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            // 特例直接返回
            if (head == null) {
                return head;
            }
            // 通过提示 先计算长度，再取模。简化 k
            int size = 0;
            ListNode index = head;
            while (index != null) {
                index = index.next;
                size++;
            }
            k = k % size;

            // 这里就是用过的双指针了
            ListNode first = head;
            ListNode last = head;

            for (int i = 0; i < k; i++) {
                last = last.next;
            }
            while (last.next != null) {
                first = first.next;
                last = last.next;
            }

            // 先成环
            last.next = head;
            // 再从 k 处断开
            ListNode ans = first.next;
            first.next = null;
            return ans;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}